# 给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。
#  若可行，输出任意可行的结果。若不可行，返回空字符串。
#
#  示例 1:
# 输入: S = "aab"
# 输出: "aba"
#
#  示例 2:
# 输入: S = "aaab"
# 输出: ""
import heapq
from collections import Counter


class Solution:
    def reorganizeString2(self, s: str) -> str:
        """
        基于计数的贪心
        :param s:
        :return:
        """
        pass

    def reorganizeString1(self, s: str) -> str:
        """
        贪心 + 大根堆
        :param s:
        :return:
        """
        res = []
        countDict = Counter(s)
        maxCount = max(countDict.items(), key=lambda e: e[1])[1]
        if maxCount > (len(s) + 1) // 2:  # 某个字符的个数大于 (len + 1) / 2 说明不能重构
            return ''
        heap = [(-e[1], e[0]) for e in countDict.items()]
        heapq.heapify(heap)
        while len(heap) > 1:  # 每次poll出剩余个数最多的两个字符(贪心策略)，并拼接到新字符串上
            _1, char1 = heapq.heappop(heap)
            _2, char2 = heapq.heappop(heap)
            res.extend([char1, char2])
            countDict[char1] -= 1
            countDict[char2] -= 1
            if countDict[char1] > 0:  # 如果char1还没重构完毕，就需要将其再次入堆
                heapq.heappush(heap, (-countDict[char1], char1))
            if countDict[char2] > 0:  # 如果char2还没重构完毕，就需要将其再次入堆
                heapq.heappush(heap, (-countDict[char2], char2))

        if heap:
            res.append(heap[0][1])
        return ''.join(res)

    def reorganizeString(self, s: str) -> str:
        return self.reorganizeString1(s)


if __name__ == "__main__":
    s = 'aab'
    print(Solution().reorganizeString(s))
